"""
213. 打家劫舍 II
已解答
中等
相关标签
相关企业
提示
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。



示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：

输入：nums = [1,2,3]
输出：3


提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000
"""
class P213(object):

    def rob(self, nums):

        """
        分开计算，要么取第一家要么最后一家
        :param nums:
        :return:
        """
        len1 = len(nums)
        if len1 == 1:
            return nums[0]
        if len1 == 2:
            return max(nums[0],nums[1])
        return max(rob_res1(nums[:-1]),rob_res1(nums[1:]))
def rob_res1(nums):
    if len(nums) == 0:
        return 0

    # 子问题：
    # f(k) = 偷 [0..k) 房间中的最大金额

    # f(0) = 0
    # f(1) = nums[0]
    # f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }

    N = len(nums)
    dp = [0] * (N + 1)
    dp[0] = 0
    dp[1] = nums[0]
    for k in range(2, N + 1):
        # max(dp[k-1]代表不取当前
        # nums[k-1] + dp[k-2] 代表取当前，nums[k-1]是因为dp的索引大了1，本质上就是nums[i] + dp[i - 2]
        dp[k] = max(dp[k - 1], nums[k - 1] + dp[k - 2])
    return dp[N]



    def rob_err1(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        思路：通过一个状态status,记录每个阶段是否有取第一个数
        初始状态为true代表取了第一位数，因为刚开始是肯定要取第一个数的
        后续每次判断nums[i] + dp[i-2] > dp[i-1] 都要statu = ! status 代表和上次取的数不同
        """
        len1 = len(nums)
        if len1 == 1:
            return nums[0]
        if len1 == 2:
            return max(nums[0],nums[1])
        dp = [0] * len1
        sDP = [0] * len1
        dp[0] = nums[0]
        sDP[0] = True

        dp[1] = max(nums[0],nums[1])
        sDP[1] = nums[0] > nums[1]

        for i in range(2, len1-1):
            if nums[i] + dp[i-2] > dp[i-1]:
                dp[i] = nums[i] + dp[i-2]
                sDP[i] = sDP[i-2]
            else:
                dp[i] = dp[i-1]
                sDP[i] = sDP[i-1]
        if sDP[len1-3]:
            #如果是true说明取了第一位
            dp[len1 - 1] = max(dp[len1 - 2], dp[len1 - 3] + nums[len1 - 1] - nums[0])
        else:
            dp[len1 - 1] = max(dp[len1 - 2], dp[len1 - 3] + nums[len1 - 1])
        return dp[len1 - 1]

# [200,3,140,20,10]
# print(P213().rob([200,3,140,20,10]))
# print(P213().rob([1,1,1,2])) # 3
print(P213().rob([2,2,4,3,2,5])) # 10